// 1. 插入排序
pub fn insertion_sort(v: &mut Vec<u8>, s: usize, e: usize) {
    for i in (s + 1)..=e {
        let key = v[i];
        let mut temp = i;
        println!("i: {}", i);
        for j in (s..=(i - 1)).rev() {
            if v[j] >= key {
                v[j + 1] = v[j];
                temp = j;
            } else {
                temp = j + 1;
                break;
            }
            println!("j: {}\nv: {:?}", j, v);
        }
        println!("temp: {}", temp);
        v[temp] = key;
        println!("v: {:?}", v);
        println!("--------------");
    }
}

// 2. 二进制数相加----2.1-4
pub fn e_2(a: Vec<u8>, b: Vec<u8>) -> Vec<u8> {
    let mut c = 0;
    let mut temp: u8;
    let len_tmep = a.len();
    let mut res = vec![0; len_tmep + 1];
    for i in (0..a.len()).rev() {
        temp = a[i] + b[i] + c;
        if temp > 1 {
            res[i + 1] = temp & 1;
            c = 1;
        } else {
            res[i + 1] = temp;
            c = 0;
        }
    }
    if c == 1 {
        res[0] = 1;
    }
    res
}

// 3. 排序---选择算法----2.2-2
pub fn select_sert(v: &mut Vec<u8>) {
    let mut index: usize;
    let mut temp;
    for i in 0..(v.len() - 1) {
        temp = v[i];
        index = i;
        for j in i..(v.len()) {
            if v[j] < temp {
                index = j;
                temp = v[j];
            }
        }
        println!("v: {:?}", v);
        println!("i: {}, v[i]: {}, index: {}, min: {}", i, v[i], index, temp);
        v[index] = v[i];
        v[i] = temp;
        println!("v: {:?}\n", v);
    }
}

// 4. 排序---归并算法
// 哨兵版
#[allow(dead_code)]
fn merge(v: &mut Vec<u8>, p: usize, q: usize, e: usize) {
    let n1 = q - p + 1;
    let n2 = e - q;
    let mut l = vec![0; n1 + 1];
    let mut r = vec![0; n2 + 1];
    for i in 0..n1 {
        l[i] = v[p + i];
    }
    for i in 0..n2 {
        r[i] = v[q + 1 + i];
    }
    l[n1] = u8::MAX;
    r[n2] = u8::MAX;
    println!("v: {:?}", v);
    println!("p: {}, q: {}, e: {}", p, q, e);
    println!("L: {:?}\nR: {:?}", l, r);
    let mut i = 0;
    let mut j = 0;
    for k in p..=e {
        if l[i] >= r[j] {
            v[k] = l[i];
            i = i + 1;
        } else {
            v[k] = r[j];
            j = j + 1;
        }
    }
    println!("v: {:?}", v);
    println!("------------------------------------");
}

// 去掉哨兵---2.3-2
fn merge_v2(v: &mut Vec<u8>, p: usize, q: usize, e: usize) {
    let n1 = q - p + 1;
    let n2 = e - q;
    let mut l = vec![0; n1];
    let mut r = vec![0; n2];
    for i in 0..n1 {
        l[i] = v[p + i];
    }
    for i in 0..n2 {
        r[i] = v[q + 1 + i];
    }
    println!("v: {:?}", v);
    println!("p: {}, q: {}, e: {}", p, q, e);
    println!("L: {:?}\nR: {:?}", l, r);
    let mut i = 0;
    let mut j = 0;
    for k in p..=e {
        if l[i] <= r[j] {
            v[k] = l[i];
            i = i + 1;
            if i == n1 {
                for m in (k + 1)..=e {
                    v[m] = r[j];
                    j = j + 1;
                }
                break;
            }
        } else {
            v[k] = r[j];
            j = j + 1;
            if j == n2 {
                for m in (k + 1)..=e {
                    v[m] = l[i];
                    i = i + 1;
                }
                break;
            }
        }
    }
    println!("v: {:?}", v);
    println!("------------------------------------");
}

pub fn merge_sort(v: &mut Vec<u8>, p: usize, r: usize) {
    if p < r {
        let q = (p + r) / 2;
        println!("merge_sort---p: {}, q: {}, r: {}", p, q, r);
        merge_sort(v, p, q);
        merge_sort(v, q + 1, r);
        merge_v2(v, p, q, r);
    }
}

// 5. 二分查找法---2.3-5
pub fn divide_serch(v: Vec<u8>, p: usize, q: usize, aim: u8) -> Option<usize> {
    if p == q {
        return None;
    }
    let mut mid = (p + q) / 2;
    let temp = v[mid];
    println!("p: {}, mid: {}, q: {}", p, mid, q);
    if temp < aim {
        mid = divide_serch(v, mid, q, aim).unwrap();
    } else if temp > aim {
        mid = divide_serch(v, p, mid, aim).unwrap();
    }
    return Some(mid);
}

// 6. 归并排序联合插入排序---2-1
pub fn merge_sort_and_insert_sort(v: &mut Vec<u8>, p: usize, r: usize, k: usize) {
    if p < r {
        let q = (p + r) / 2;
        println!("Sortting\np: {}, q: {}, r: {}", p, q, r);
        if q - p + 1 <= k {
            println!("The data is sort by insertion......");
            insertion_sort(v, p, q);
            insertion_sort(v, q + 1, r);
        } else {
            println!("The data is sort by merge......");
            merge_sort_and_insert_sort(v, p, q, k);
            merge_sort_and_insert_sort(v, q + 1, r, k);
        }
        merge_v2(v, p, q, r);
    }
}

// 7. 冒泡排序---2-2
pub fn bubble_sort(v: &mut Vec<u8>) {
    let mut temp;
    for i in 1..(v.len() - 1) {
        for j in (i..=(v.len() - 1)).rev() {
            if v[j] < v[j - 1] {
                temp = v[j];
                v[j] = v[j - 1];
                v[j - 1] = temp;
            }
        }
        println!(
            "i: {}\nv: {:?}\n-------------------------------------------",
            i, v
        );
    }
}

// 8. 霍纳规则，求值多项式---2-3
pub fn horner(a: Vec<i32>, x: i32) -> i32 {
    let mut y = 0;
    for i in (0..a.len()).rev() {
        y = a[i] + x * y;
    }
    y
}

// 9. 逆序对---2-4
fn inversion(v: &Vec<u8>, p: usize, q: usize, r: usize) {
    println!("p: {}, q: {}, r: {}", p, q, r);
    for i in p..=q {
        for j in (q + 1)..=r {
            if v[i] > v[j] {
                println!("({}, {})", i, j);
            }
        }
    }
}

pub fn insertion_search(v: &Vec<u8>, p: usize, r: usize) {
    if p < r {
        let q = (p + r) / 2;
        insertion_search(v, p, q);
        insertion_search(v, q + 1, r);
        inversion(v, p, q, r);
    }
}
